package graph;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.ArrayList;

/**
 * A directed graph data structure.
 * 
 * @author Scott.Stark@jboss.org
 * @version $Revision$
 * @param 
 */
@SuppressWarnings("unchecked")
public class Graph {
//	/** Color used to mark unvisited nodes */
//	public static final int VISIT_COLOR_WHITE = 1;
//
//	/** Color used to mark nodes as they are first visited in DFS order */
//	public static final int VISIT_COLOR_GREY = 2;
//
//	/** Color used to mark nodes after descendants are completely visited */
//	public static final int VISIT_COLOR_BLACK = 3;

	/** Vector<Vertex> of graph vertices */
	private ArrayList<Vertex> vertices;

	/** Vector<Edge> of edges in the graph */
	private ArrayList<Edge> edges;


	/**
	 * Construct a new graph without any vertices or edges
	 */
	public Graph() {
		vertices = new ArrayList<Vertex>();
		edges = new ArrayList<Edge>();
	}

	/**
	 * Are there any vertices in the graph
	 * 
	 * @return true if there are no vertices in the graph
	 */
	public boolean isEmpty() {
		return vertices.size() == 0;
	}

	/**
	 * Add a vertex to the graph
	 * 
	 * @param v
	 *            the Vertex to add
	 * @return true if the vertex was added, false if it was already in the
	 *         graph.
	 */
	public boolean addVertex(Vertex v) {
		boolean added = false;
		if (vertices.contains(v) == false) {
			added = vertices.add(v);
		}
		return added;
	}
	
	public boolean addEdges(Edge e) {

		boolean added = false;
		if (edges.contains(e) == false) {
			added = edges.add(e);
		}
		return added;
	}

	/**
	 * Get the vertex count.
	 * 
	 * @return the number of vertices in the graph.
	 */
	public int size() {
		return vertices.size();
	}





	/**
	 * Get the given Vertex.
	 * 
	 * @param n
	 *            the index [0, size()-1] of the Vertex to access
	 * @return the nth Vertex
	 */
	public Vertex getVertex(int n) {
		return vertices.get(n);
	}

	/**
	 * Get the graph getVertices
	 * 
	 * @return the graph getVertices
	 */
	public ArrayList<Vertex> getVertices() {
		return this.vertices;
	}

	/**
	 * Insert a directed, weighted Edge into the graph.
	 * 
	 * @param from
	 *            - the Edge starting vertex
	 * @param to
	 *            - the Edge ending vertex
	 * @param cost
	 *            - the Edge weight/cost
	 * @return true if the Edge was added, false if from already has this
	 *         Edge
	 * @throws IllegalArgumentException
	 *             if from/to are not vertices in the graph
	 */
	public boolean addEdge(Vertex from, Vertex to, int cost)
			throws IllegalArgumentException {
		if (vertices.contains(from) == false)
			throw new IllegalArgumentException("from is not in graph");
		if (vertices.contains(to) == false)
			throw new IllegalArgumentException("to is not in graph");

		Edge e = new Edge(from, to, cost);
		if (from.findEdge(to) != null)
			return false;
		else {
			from.addEdge(e);
			to.addEdge(e);
			edges.add(e);
			return true;
		}
	}

//	/**
//	 * Insert a bidirectional Edge in the graph
//	 * 
//	 * @param from
//	 *            - the Edge starting vertex
//	 * @param to
//	 *            - the Edge ending vertex
//	 * @param cost
//	 *            - the Edge weight/cost
//	 * @return true if edges between both nodes were added, false otherwise
//	 * @throws IllegalArgumentException
//	 *             if from/to are not vertices in the graph
//	 */
//	public boolean insertBiEdge(Vertex from, Vertex to, int cost)
//			throws IllegalArgumentException {
//		return addEdge(from, to, cost) && addEdge(to, from, cost);
//	}

	/**
	 * Get the graph edges
	 * 
	 * @return the graph edges
	 */
	public ArrayList<Edge> getEdges() {
		return this.edges;
	}

	/**
	 * Remove a vertex from the graph
	 * 
	 * @param v
	 *            the Vertex to remove
	 * @return true if the Vertex was removed
	 */
	public boolean removeVertex(Vertex v) {
		if (!vertices.contains(v))
			return false;

		vertices.remove(v);

		// Remove the edges associated with v
		for (int n = 0; n < v.getOutgoingEdgeCount(); n++) {
			Edge e = v.getOutgoingEdge(n);
			v.remove(e);
			Vertex to = e.getTo();
			to.remove(e);
			edges.remove(e);
		}
		for (int n = 0; n < v.getIncomingEdgeCount(); n++) {
			Edge e = v.getIncomingEdge(n);
			v.remove(e);
			Vertex predecessor = e.getFrom();
			predecessor.remove(e);
		}
		return true;
	}

	/**
	 * Remove an Edge from the graph
	 * 
	 * @param from
	 *            - the Edge starting vertex
	 * @param to
	 *            - the Edge ending vertex
	 * @return true if the Edge exists, false otherwise
	 */
	public boolean removeEdge(Vertex from, Vertex to) {
		Edge e = from.findEdge(to);
		if (e == null)
			return false;
		else {
			from.remove(e);
			to.remove(e);
			edges.remove(e);
			return true;
		}
	}

//	/**
//	 * Clear the mark state of all vertices in the graph by calling clearMark()
//	 * on all vertices.
//	 * 
//	 * @see Vertex#clearMark()
//	 */
//	public void clearMark() {
//		for (Vertex w : vertices)
//			w.clearMark();
//	}

	/**
	 * Clear the mark state of all edges in the graph by calling clearMark() on
	 * all edges.
	 */
	public void clearEdges() {
		for (Edge e : edges)
			e.clearMark();
	}

	/**
	 * Search the vertices for one with Type.
	 * 
	 * @param Type
	 *            - the vertex Type
	 * @return the first vertex with a matching Type, null if no matches are
	 *         found
	 */
	public ArrayList<Vertex> findVerticesByType(Class<?> type) {
		ArrayList<Vertex> match = new ArrayList<Vertex>();
		for (Vertex v : vertices) {
			if (type.equals(v.getType())) {
				match.add(v);
			}
		}
		if(match.size() != 0)
			return match;
		else
			return null;
	}

	/**
	 * Search the vertices for one with data.
	 * 
	 * @param data
	 *            - the vertex data to match
	 * @param compare
	 *            - the comparator to perform the match
	 * @return the first vertex with a matching data, null if no matches are
	 *         found
	 */
	public Vertex findVertexByData(Object data) {
		Vertex match = null;
		for (Vertex v : vertices) {
			if (data == v.getData()) {
				match = v;
				break;
			}
		}
		return match;
	}

//	/**
//	 * Search the graph for cycles. In order to detect cycles, we use a modified
//	 * depth first search called a colored DFS. All nodes are initially marked
//	 * white. When a node is encountered, it is marked grey, and when its
//	 * descendants are completely visited, it is marked black. If a grey node is
//	 * ever encountered, then there is a cycle.
//	 * 
//	 * @return the edges that form cycles in the graph. The array will be empty
//	 *         if there are no cycles.
//	 */
//	public Edge[] findCycles() {
//		ArrayList<Edge> cycleEdges = new ArrayList<Edge>();
//		// Mark all vertices as white
//		for (int n = 0; n < vertices.size(); n++) {
//			Vertex v = getVertex(n);
//			v.setMarkState(VISIT_COLOR_WHITE);
//		}
//		for (int n = 0; n < vertices.size(); n++) {
//			Vertex v = getVertex(n);
//			visit(v, cycleEdges);
//		}
//
//		Edge[] cycles = new Edge[cycleEdges.size()];
//		cycleEdges.toArray(cycles);
//		return cycles;
//	}
//
//	private void visit(Vertex v, ArrayList<Edge> cycleEdges) {
//		v.setMarkState(VISIT_COLOR_GREY);
//		int count = v.getOutgoingEdgeCount();
//		for (int n = 0; n < count; n++) {
//			Edge e = v.getOutgoingEdge(n);
//			Vertex u = e.getTo();
//			if (u.getMarkState() == VISIT_COLOR_GREY) {
//				// A cycle Edge
//				cycleEdges.add(e);
//			} else if (u.getMarkState() == VISIT_COLOR_WHITE) {
//				visit(u, cycleEdges);
//			}
//		}
//		v.setMarkState(VISIT_COLOR_BLACK);
//	}

	public String toString() {
		StringBuffer tmp = new StringBuffer("Graph[");
		for (Vertex v : vertices)
			tmp.append(v);
		tmp.append(']');
		return tmp.toString();
	}

	/**
	 * ** *
	 ** **/

	public ArrayList<Vertex> findVerticsByTypeFromVertex(Class<?> type, Vertex currentVertex) {


		ArrayList<Vertex> resultVertices = new ArrayList<Vertex>();
		
		
		findVerticsByTypeFromVertexOutgoing(type, currentVertex, resultVertices);
		
		if(resultVertices.size() == 0) {
			findVerticsByTypeFromVertexIncoming(type, currentVertex, resultVertices);
		}
		
		
		return resultVertices;
	
	}
	
	public ArrayList<Vertex> findVerticsByTypeFromVertexOutgoing(Class<?> type, Vertex currentVertex, ArrayList<Vertex> resultVertices) {

		ArrayList<Edge> currentVertexEdges = currentVertex.getOutgoingEdges();


		Vertex vertex;

		for (Edge e : currentVertexEdges) {
			vertex = e.getTo();
			if (vertex.getType().equals(type) && !resultVertices.contains(vertex)) {
				resultVertices.add(vertex);
			}
			findVerticsByTypeFromVertexOutgoing(type, vertex, resultVertices);
		}
		


		return resultVertices;

	}
	
	public ArrayList<Vertex> findVerticsByTypeFromVertexIncoming(Class<?> type, Vertex currentVertex, ArrayList<Vertex> resultVertices) {

		ArrayList<Edge> currentVertexEdges = currentVertex.getIncomingEdges();
		
		Vertex vertex;
		
		for (Edge e : currentVertexEdges) {
			vertex = e.getFrom();
			if (vertex.getType().equals(type) && !resultVertices.contains(vertex)) {
				resultVertices.add(vertex);
			}
			findVerticsByTypeFromVertexIncoming(type, vertex, resultVertices);
		}
		return resultVertices;
	}
	
	public Graph shadowCopy(){
		Graph newGraph=new Graph();
		for(Vertex v:vertices){
			newGraph.addVertex(v);
		}
		for(Edge e:edges){
			newGraph.addEdges(e);
		}
		return newGraph;
	}
	

	/**
	 * ** *
	 ** **/

}